//二分查找
//利用数组本身有序，通过二分查找插入位置
public class BinarySearch {

    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) return -1;
        int l = 0, r = n - 1;
        while (l < r) {
            //计算mid
            int mid = l + r + 1 >> 1;
            //如果中点比目标要小，说明插入位置在右段，把 l 往移动到 mid
            if (nums[mid] <= target) {
                l = mid;
            } else {
                //否则说明插入位置再左端，把 r 移动到 mid
                r = mid - 1;
            }
        }
        return nums[r] == target ? r : -1;
    }

}
